今天來點輕鬆的挑戰吧！誰不想在股市裡買低賣高、狠狠賺上一筆呢？
想像一下：你手上有一份神秘的股價清單，你只需要在適當的時機買進賣出，就能成為股票小神通！
但等等，Leetcode 就是這麼無情...只有一次機會讓你選最佳買賣日！來吧，讓我們一起看看如何用 TypeScript 來解決這個問題！💪

題目

Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

你會得到一個名為 prices 的陣列，prices[i] 代表某個股票在第 i 天的價格。

你想最大化利潤，通過選擇 某一天 買入股票，並選擇 未來的某一天 賣出該股票。

返回能夠實現的最大利潤。如果無法實現利潤，則返回 0。

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

在第 2 天以 1 元買入，並在第 5 天以 6 元賣出，利潤 = 6 - 1 = 5。
注意，你不能在第 2 天之後的日子買入並在之前的日子賣出喔。

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

這種情況下無法進行任何交易，最大利潤為 0。

實作

function maxProfit(prices: number[]): number {
    let minPrice = Number.MAX_VALUE;
    let maxProfit = 0;

    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice;
        }
    }

    return maxProfit;
}

這段程式碼的思路是：

1. 從頭到尾迴圈陣列，我們不斷更新目前遇到的最低價位，這是潛在的最佳買入點。
2. 當我們遇到比之前價格高的日子時，計算可能的利潤，並更新最大利潤。

解題脈絡：

就是低買高賣，這題核心在於如何找到最佳的買賣時機。面對每天不同的股價，我們的目標是找出一個最佳的買入價格以及對應的最佳賣出價格。

1. 最低價策略：在遍歷價格陣列的過程中，我們隨時關注當前的最低價格，因為這將成為潛在的最佳買入點。只要價格比之前的低，我們就將這個價格記住。

2. 最大利潤計算：一旦遇到一個高於目前最低價的價格，這代表我們可以賣出，並計算賣出後的潛在利潤。然後我們比較這個利潤是否是目前最大的，若是，就更新最大利潤。

3. 單次遍歷的優勢：這種解法只需要遍歷陣列一次，避免了暴力解法中需要雙層迴圈去計算每一個買賣對應的情況。這樣的時間複雜度為 O(n)，相對於暴力解法的 O(n²) 更加高效。

本次要點：

• 找出最低價格並儲存，從後續天數開始尋找最大利潤。
• 單次迴圈解法，時間複雜度 O(n)。

希望今天的分享，可以幫助大家發大財
⎛⎝(•‿•)⎠⎞ ⎛⎝(•‿•)⎠⎞ ⎛⎝(•‿•)⎠⎞